/* 
 * File:   m_rbtree.h
 * Author: tangchao
 *
 * Created on 2013年6月14日, 上午10:49
 */

#ifndef M_RBTREE_H
#define	M_RBTREE_H

#ifdef	__cplusplus
extern "C"
{
#endif

    #define	RB_RED		0
#define	RB_BLACK	1

    struct rb_node
    {
        unsigned long __rb_parent_color;
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    }
    __attribute__((aligned(sizeof (long))));

    /* The alignment might seem pointless, but allegedly CRIS needs it */

    struct rb_root
    {
        struct rb_node *rb_node;
    };


#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)

    /* 'empty' nodes are nodes that are known not to be inserted in an rbree */
#define RB_EMPTY_NODE(node)  \
	((node)->__rb_parent_color == (unsigned long)(node))
#define RB_CLEAR_NODE(node)  \
	((node)->__rb_parent_color = (unsigned long)(node))


    extern void rb_insert_color(struct rb_node *, struct rb_root *);
    extern void rb_erase(struct rb_node *, struct rb_root *);


    /* Find logical next and previous nodes in a tree */
    extern struct rb_node *rb_next(const struct rb_node *);
    extern struct rb_node *rb_prev(const struct rb_node *);
    extern struct rb_node *rb_first(const struct rb_root *);
    extern struct rb_node *rb_last(const struct rb_root *);

    /* Fast replacement of a single node without remove/rebalance/add/rebalance */
    extern void rb_replace_node(struct rb_node *victim, struct rb_node * new,
            struct rb_root *root);

    static inline void
    rb_link_node(struct rb_node * node, struct rb_node * parent,
            struct rb_node ** rb_link)
    {
        node->__rb_parent_color = (unsigned long) parent;
        node->rb_left = node->rb_right = NULL;

        *rb_link = node;
    }



#ifdef	__cplusplus
}
#endif

#endif	/* M_RBTREE_H */

